// 快速排序
function merge(arr) {
    mergeSort(arr, 0, arr.length - 1)
}

function mergeSort(arr, s, e) {
    if (s >= e) return
    let i = s, j = s;
    let p = arr[e]
    while(j < e) {
        if (arr[j] <= p) {
            const tmp = arr[i]
            arr[i] = arr[j]
            arr[j] = tmp
            i++
        }
        j++
    }
    arr[e] = arr[i]
    arr[i] = p
    mergeSort(arr, s, i - 1)
    mergeSort(arr, i + 1, e)
}
var arr = [5, 3, 2, 10, 8, 6, 7, 1, 4, 9]
merge(arr)
console.log(arr)

// 快排3.0
{
    function sort(arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        quickSort(arr, 0, arr.length - 1)
    }
    function quickSort(arr, s, e) {
        if (s < e) {
            let tmpArr = partition(arr, s, e);
            quickSort(arr, s, tmpArr[0] - 1);
            quickSort(arr, tmpArr[1] + 1, e)
        }
    }
    function partition(arr, L, R) {
        let less = L - 1;
        let more = R;
        let i = L;
        let p = arr[R]
        while(i < more) {
            if (arr[i] < p) {
                less++
                const tmp = arr[less]
                arr[less] = arr[i]
                arr[i] = tmp
                i++;
            }
            if (arr[i] == p) {
                i++
            }
            if (arr[i] > p) {
                more--
                const tmp = arr[more]
                arr[more] = arr[i]
                arr[i] = tmp
            }
        }
        const tmp = arr[more]
        arr[more] = arr[R]
        arr[R] = tmp
        console.log('part----', less+1, more)
        console.log(arr)
        return [less + 1, more]
    }
    // let arr = [4, 6, 1, 5, 3, 5]
    var arr = [5, 3, 2, 10, 8, 6, 7, 1, 4, 9, 5, 2, 5]
    sort(arr)
    console.log(arr)
}

// 快排查找第K大元素 时间复杂度O(n) 首次遍历n，之后每次分区后遍历都除以2 n + n/2 + n/4 + n/8
function getMaxK(arr, k) {
    // 从小打到排序，第k大的元素的下标为length - k
    const maxI = arr.length - k
    var s = mergeMaxSort(arr, maxI, 0, arr.length - 1)
    console.log(`第${k}大元素为：`,s)
    return s

}
function mergeMaxSort(arr, maxI, s, e) {
    // 区间变成一个时也是结束条件，恰好找到
    if (s >= e) return arr[s]
    let i = s, j = s;
    let p = arr[e]
    while(j < e) {
        if (arr[j] <= p) {
            const tmp = arr[i]
            arr[i] = arr[j]
            arr[j] = tmp
            i++
        }
        j++
    }
    arr[e] = arr[i]
    arr[i] = p

    // 相等时恰好找到
    if (maxI === i) {
        console.log(arr[i])
        return arr[i]
    } else if (maxI > i) {
        // 不要忘记写return
        return mergeMaxSort(arr, maxI, i + 1, e)
    } else {
        return mergeMaxSort(arr, maxI, s, i - 1)
    }
}

var arr = [5, 3, 2, 10, 8, 6, 7, 1, 4, 9]
getMaxK(arr, 1)